#include <iostream>
#include <malloc.h>
#define INF 32767	//定义无穷大 
#define MAXV 100	//最大顶点个数
typedef char InfoType;
 
//定义邻接矩阵类型 
typedef struct
{
	int no;
	InfoType info;
}VertexType;
typedef struct
{
	int edges[MAXV][MAXV];
	int n,e;
	VertexType vexs[MAXV]; 
}MatGraph;

//定义邻接表类型
typedef struct ANode
{
	int adjvex;
	struct ANode *nextarc;
	int weight;
 } ArcNode;
typedef struct Vnode
{
	InfoType info;
	int count;
	ArcNode *firstarc;
}VNode;
typedef struct
{
	VNode adjlist[MAXV];
	int n,e;
}AdjGraph;

//邻接矩阵的基本运算:
//创建邻接矩阵 
void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e)
{
	int i,j; 
	g.n=n;g.e=e;
	for(i=0;i<g.n;i++)
		for(j=0;j<g.n;j++)
			g.edges[i][j]=A[i][j];
}
//输出邻接矩阵
void DispMat(MatGraph g)
{
	int i,j;
	for(i=0;i<g.n;i++)
	{
		for(j=0;j<g.n;j++)
		{
			if(g.edges[i][j]!=INF)
				printf("%4d",g.edges[i][j]);
			else
				printf("%4s","-");
		}
		printf("\n");
	}
 } 
 
 //邻接表的基本运算：
 //创建邻接表 
 void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) 
 {
 	int i,j;
	ArcNode *p;
	G=(AdjGraph *)malloc(sizeof(AdjGraph));
	for(i=0;i<n;i++)
		G->adjlist[i].firstarc=NULL;
	for(i=0;i<n;i++)
	{
		for(j=n-1;j>=0;j--)
		{
			if(A[i][j]!=0&&A[i][j]!=INF)
			{
				p=(ArcNode *)malloc(sizeof(ArcNode));
				p->adjvex=j;
				p->weight=A[i][j];
				p->nextarc=G->adjlist[i].firstarc;
				G->adjlist[i].firstarc=p;
			}
		}
	}
	G->n=n;G->e=n;
 } 
 //输出邻接表
 void DispAdj(AdjGraph *G)
 {
 	int i;
 	ArcNode *p;
 	for(i=0;i<G->n;i++)
 	{
 		p=G->adjlist[i].firstarc;
 		printf("%3d:",i);
 		while(p!=NULL)
 		{
 			printf("%3d[%d]->",p->adjvex,p->weight);
 			p=p->nextarc ;
		 }
		printf("^\n");
	 }
  } 
//销毁邻接表
void DestroyAdj(AdjGraph *&G)
{
	int i;
	ArcNode *pre,*p;
	for(i=0;i<G->n;i++)
	{
		pre=G->adjlist[i].firstarc;
		if(pre!=NULL)
		{
			p=pre->nextarc ;
			while(p!=NULL)
			{
				free(pre);
				pre=p;p=p->nextarc ;
			}
			free(pre);
		}
	 } 
	 free(G);
 } 
int main()
{
	MatGraph g;
	AdjGraph *G;
	int A[MAXV][MAXV]={{0,1,0,1,0,0},
						{0,0,1,0,0,0},
						{1,0,0,0,0,1},
						{0,0,1,0,0,1},
						{0,0,0,1,0,0},
						{1,0,0,0,1,0}};
	int n=6,e=10;
	CreateMat(g,A,n,e);
	printf("图G的邻接矩阵：\n");
	DispMat(g);
	CreateAdj(G,A,n,e);
	printf("图G的邻接表：\n");
	DispAdj(G);
	DestroyAdj(G);
	return 1; 
} 
